COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.S BASIC RESEARCH IN ARTIFICIAL INTELLIGENCE AND FORMAL REASONING
C00022 00003	GENERAL SUMMARY OF FORMAL REASONING WORK
C00023 ENDMK
C⊗;
.S BASIC RESEARCH IN ARTIFICIAL INTELLIGENCE AND FORMAL REASONING

	Applied research requires basic research to replenish the stock
of ideas on which its progress depends.

	The long range goals of work in basic AI and formal reasoning
are the same as described in our last proposal - to make computers
carry out the reasoning required to solve problems.  However,
recent discoveries have made it easier to apply our main tool,
first order logic, both to AI and to proving programs correct.
This brings application nearer, especially to proving programs
and hardware
correct, and has changed the direction of some of our research.

We begin with an outline of our new point of view and its relation
to applications.  The work has both theoretical and experimental
components.

NEW DIRECTIONS

For data bases to include many types of information that decision makers
really need will require major advances in representation theory.
Programs that use the information effectively impose requirements on
the representationa and also need new modes of reasoning.
Thus current
data base technology at best allows simple relations to be represented - 
e.g. "Smith is the supervisor of Jones."  Additions from current AI techniqes
would allow simple generalizations of relations ("Every employee has a supervisor
except the director."), but this leaves a tremendous range of representation
problems untreated:

1. Mental states - what a person believes, knows, wants, fears, etc.
2. Modalities - what may happen, what must happen, what ought to be done, what
      can be done, etc.
3. Counterfactual conditionals - if something were true what else would be the case.
4. Causality
5. Actions and their modifiers.

None of these concepts can be adequately handled at present, and there are
undoubtedly other phenomena which are yet to be discovered.  What is needed
here is some good basic theory.

Since much of our research is necessarily very technical,
before we elaborate our recent results and future plans,
we will present a hypothetical example of an applied AI program
whose success will depend on solving the problems we are studying

ANALYST - AN EXAMPLE OF A FUTURE APPLICATION

ANALYST scans a computerized %2intelligence%1 data base.  (We italicize
the word "intelligence" when used in the military sense).  It looks
for patterns of information that suggest conjectures about an
adversary's capabilities, intentions, knowledge, beliefs and goals.
When ANALYST thinks it has found something significant, it informs
a human analyst.  Its %2forte%1 is examining more data than is possible
for a human and guaranteeing that all possibilities of the kinds
it is programmed for are pursued.  The example is somewhat contrived,
because we have
emphasized the problems we are currently studying and ignored others.
Moreover, an
ANALYST that could be programmed on the basis of present knowledge
would be very limited in its capabilities, partly because we have only
partly solved the problems we are studying, but mainly because of problems
no-one has begun to study.

Suppose ANALYST reads in a report from Damascus,

%2Major Alexei Ivanov went to Damascus airport, bought a ticket to
Moscow for cash, and departed on the next flight to Moscow%1.

	ANALYST asks itelf why Ivanov did what he did.  Usually it
finds hypotheses that fit a normal pattern of behavior and gains
nothing but further defining the normal pattern.  Let's suppose there
is more in this case.

	%2Why did he pay cash%1?  This question arises from a program
that looks for deviations from the normal pattern.  We suppose that
it has been determined that Russians usually buy tickets from their
travel agency Intourist.  The conjecture is then formed that Ivanov
is in a hurry and that some event has required him to go to Moscow
suddenly.
The hypothesis is confirmed by discovering that he had previously
accepted an invitation incompatible with a Moscow trip.

	Now suppose that it is known or conjectured that Ivanov is
a radar expert.  This leads ANALYST to scan facts about our adversary
relationship with the Russians in the field of radar including the
fact that we are trying to find out the pattern of frequency variation
of their radars.  One general fact in the data base is that when one
side finds out the frequency variation pattern of a radar, the other
side wants to change it.  Therefore, analyst conjectures that the
Russians think we will soon know the freqency variation pattern of
their R111 radar.

	This example poses several problems not handled by present
database programs.  First, present data base systems store particular
facts, not general facts.  Any general facts usually have to be built
into programs or at least into productions.
Second, the laws that determine what conclusions can
be drawn from facts about knowledge, belief and intentions are different
from thosee governing non mental qualities.
Third,
the reasoning required even to conjecture that Ivanov is in a hurry
involves conjecturing that his behavior is normal except in so far
as it is known to be abnormal.
Fourth, many reasoning processes involve observation as well as
reasoning from facts in a data base.  Obtaining the confirming evidence
that Ivanov is in a hurry has that character.
Finally, the pattern
recognition required to conjecture from Ivanov's hurried Moscow trip
and the previously known facts that they think we will soon know
their radar pattern is quite different from that done today.
We shall consider these problems in turn.

Representing general facts:

Few existing data base systems represent general facts by entries in
the data base.
For example, ANALYST needs to represent the fact that the Russians
almost always buy their airline tickets from Intourist in such a way
that further deductions can be made and the fact can be modified by
new evidence.
Existing systems represent them by program or by
%2semi-programs%1 like productions.  This works very well for applying
the general facts to particular cases,
but it doesn't work well for deducing new
general facts from old ones or representing facts about facts.
In order to represent
such facts one needs quantifiers, and the most developed logical system
with quantifiers is first order logic.  Even within first order logic,
there are many possible ways of representing a particular kind of fact,
and much further study is required.

Knowledge and belief:

	The notion %2X thinks Y will soon know Z%1 is not unusually
complex when adversaries try to outwit each other, but it presents
problems for machine representation that haven't been conclusively
solved but on which we have made recent progress.

	The simplest way to represent such a sentence in a computer
fact in a computer might be by a Lisp expression like

	(THINKS X (SOON (KNOW Y Z))).

However, ANALYST must do much more than just represent it.  It must
be able to prove or conjecture it under appropriate circumstances
and it must be able to draw correct conclusions from it - and not
draw incorrect conclusions.  The latter is the the more immediate
problem.  Let us return to simplified examples and suppose we have
the sentences
%2Pat knows Mike's telephone number%1 and %2Mike's telephone number
is the same as Mary's%1.  These might be represented as
(KNOW PAT (TELEPHONE MIKE)) and (EQUAL (TELEPHONE MIKE) (TELEPHONE MARY)).
A computerized deduction system that uses the rule that equals may be
substituted for equals might conclude %2Pat knows Mary's telephone
number%1 which is not a legitimate deduction, although it would
be legitimate to deduce that Pat dialed Mary's telephone number
from the fact that he dialed Mike's number and the fact that the
numbers are the same.

	The fact that substitution of equals for equals is
legitimate in some contexts and not in others has been well known
for a very long time.  Correct logical laws for handling such
cases have been proposed, but the presently known solutions have
two defects.  First they usually treat only one such function
at a time such as "knows" while real life problems often mix
up several even in the same sentence, e.g. %2They think we will
soon know ...%1.  Second, each such mental quality requires
modifying the logic.  In a practical case this would be many
months work and might have to be done again and again.

	Recently McCarthy has discovered how to represent such
facts in undmodified first order logic and the solution works
no matter how many mental qualities must be treated.  We are
The work is described in (McCarthy 1977b) and will be further
developed in the next year and a half.

Robert Moore has also found some new results on representing partial information
about knowledge and belief.  He has shown that some of the "multiple data base"
approaches of previous AI work cannot represent partial knowledge - e.g. they
cannot represent the assertion that the Russians know how many divisions the
Chinese have, unless the program knows this also,
so it can include the information in the
data base representing the Russians' model of the world.  Moore has shown how
this and related difficulties can be avoided by talking not about beliefs
themselves, but rather the possible worlds in which the beliefs are true or false.
A very elegant theory has been developed based on this approach.

	McCarthy has long been aware that standard logic does
not represent the many kinds of reasoning that people use in
forming conjectures.  This reasoning requires the ability to
conjecture that the known facts about a phenomenon are all
the relevant facts.  Thus ANALYST must conjecture that Ivanov was
in a hurry because it has no other explanation even though it
cannot conclusively exclude other explanations.

McCarthy has recently found a partial solution to this problem.
An axiom schema of first order logic called a %2minimization schema%1
can be used to represent in a flexible way the conjecture that the
entities that can be shown to exist on hte basis of the information in a certain
data base are all the relevant entities that exist.  The flexibility
comes from the fact that the set of information conjectured to be all
the relevant information is readily changed.
Martin Davis has helped in the mathematical formulation of this
method.

Reasoning with observation:

Filman has demonstrated that the chain of reasoning involved
in a chess problem requires programs that observe a chess
board as well as mathematical deduction if
the number of steps is to be feasible.  His experience with
observational reasoning shows that we still have a lot to
learn about it.


Patterns:

Many of	the patterns ANALYST will have to recognize
do not fall into the categories so far treated in AI work.
For example, explaining an unknown activity of an adversary
requires conjecturing a goal and its relation to other goals,
a belief structure that makes the goal seem desirable and
attainable, and a means of attaining the goal that gives
rise to the observations.  Present AI pattern recognition
programs find patterns in observed data rather than introduce
new entities in order to explain the data.  McCarthy is developing
a general notion of pattern, and Wilkins is using chess to develop some
advanced notions of strategic pattern.

Our object in raising these problems is not to show that present
database efforts are misdirected.  In our opinion, the problems
being explored are entirely appropriate.  However, it is necessary
to look further ahead and provide the basic research foundation
for more advanced database work.  The same basic research will
also support other intelligent system and program verification
advances, but we haven't time or space to elaborate these now.
GENERAL SUMMARY OF FORMAL REASONING WORK

	This section is similar to the corresponding section of
our previous proposal, because while there have been new discoveries,
as outlined above, the basic justification for formal reasoning
work remains the same.